<?php

class MaxHeap
{
    public $data;
    public $count=0;
    
    /**
     * 插入元素
     */
    public function create($arr)
    {
        array_map(function($v){
            $this->insert($v);
        },$arr);
    }
    
    /**
     * 上浮元素（重置堆）
     */
    public function shiftUp()
    {
        //找到数组的最后一个元素的索引
        $tmp = $this->count - 1;
        //最后那个元素的父节点
        $parent = intval(($tmp - 1)/2,NULL);
        
        //父节点大于它的子节点就进行交换的就是最小堆，反之就是最大堆
        while ($tmp > 0 && $this->data[$parent] < $this->data[$tmp])
        {
            list($this->data[$parent],$this->data[$tmp]) = array($this->data[$tmp],$this->data[$parent]);
            $tmp = $parent;
            $parent = intval(($tmp-1)/2,NULL);
        }
    }
    
    /**
     * 找到最大的值,即根节点,并重置堆
     */
    public function getMax()
    {
        //最大堆的最大值
        $max = $this->data[0];
        
        //最后一个节点作为临时节点
        $this->data[0] = $this->data[$this->count-1];
        
        //将最后一个节点赋值为0
        $this->data[--$this->count] = 0;
        
        //向下重置最大堆
        $this->shiftDown(0);
        
        return $max;
    }
    
    /**
     * 下沉节点重制最大堆
     */
    public  function shiftDown($k)
    {
        //当前节点
        $tmp = $k;
        //当前节点的左孩子
        $left = 2 * $k  + 1;
        //当前元素的右孩子
        $right = 2 * $k + 2;
        
        //如果左孩子节点存在，并左孩子节点大于当前值，那么交换索引
        if ($left<$this->count && $this->data[$left]>$this->data[$tmp])
        {
            $tmp = $left;
        }
        
        //如果右孩子节点存在，并右孩子节点大于当前值，那么交换索引
        if ($right<$this->count && $this->data[$right]>$this->data[$tmp])
        {
            $tmp = $right;
        }
        
        //如果索引发生变化,交换，递归调用
        if ($tmp != $k)
        {
            list($this->data[$tmp],$this->data[$k]) = array($this->data[$k],$this->data[$tmp]);
            $this->shiftDown($tmp);
        }
        
        //非递归调用实现
        //        //左孩子
        //        //$left = 2 * $k + 1;
        //        //右孩子
        //        //$right = 2 * $k + 2;
        //
        //        while ( (2 * $k + 1) < $this->count)
        //        {
        //            $j = 2 * $k + 1;
        //
        //            //判断是否有右孩子
        //            if (($j + 1)<$this->count && $this->data[$j+1] > $this->data[$j])
        //            {
        //                $j += 1;
        //            }
        //
        //            if ($this->data[$k] > $this->data[$j])
        //            {
        //                break;
        //            }
        //
        //            list($this->data[$k],$this->data[$j]) = array($this->data[$j],$this->data[$k]);
        //            $k = $j;
        //        }
        
    }
    
    /**
     * 插入
     */
    public function insert($v)
    {
        //第一次
        if ( $this->count == 0 )
        {
            //插入第一条数据
            $this->data[0] = $v;
            $this->count = 1;
        }
        else
        {
            //新插入的元素 放在堆的最后面
            $this->data[$this->count++] = $v;
            
            //上浮元素
            $this->shiftUp();
        }
    }
    
    public function display()
    {
        echo '最大堆:'.implode('-',$this->data);
    }
    
    public function getData()
    {
        return $this->data;
    }
    
    public function setData($v)
    {
        $this->data[0] = $v;
    }
}

$tui = new MaxHeap();
for ($i=0;$i<50;$i++)
{
    $arr[] = mt_rand(1,2000000);
}

//前10个元素构建最大堆
$brr = array_splice($arr,0,10);
$tui->create($brr);
$data = $tui->getData();
for ($i=11;$i<50;$i++)
{
    if ($arr[$i] > $data[0])
    {
        $tui->setData($arr[$i]);
        $tui->shiftDown(0);
    }
}
for ($i=0;$i<10;$i++)
{
    echo $tui->getMax().'   ';
}

